﻿#pragma once
#include <vector>
#include <unordered_map>

using namespace std;

// 并查集 元素
template<class T>
class Element
{
public:
    Element(T t)
    {
        _value = t;
    }

    ~Element()
    {

    }

private:
    T _value;
};

// 并查集结构
template<class T>
class UnionFind
{
public:
    UnionFind(vector<T> list);
    void unionElements(T t1, T t2);
    bool isTheSameHead(T t1, T t2);
    ~UnionFind();

private:
    // 查找一个元素的父节点，查找过程中，使父节点的所有子节点扁平化
    Element<T>* findHead(Element<T>* element);

private:
    unordered_map<T, Element<T>*> _elements;
    unordered_map<Element<T>*, Element<T>*> _elementsToHeads;
    unordered_map<Element<T>*, size_t> _elementSizes;
};
